/*
? 归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
? 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并
? 从下往上的归并排序：将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；得到若干个长度为2的有序数列，再将这些数列两两合并；得到若干个长度为4的有序数列，再将它们两两合并；直接合并成一个数列为止。这样就得到了我们想要的排序结果
? 从上往下的归并排序：它与"从下往上"在排序上是反方向的。它基本包括3步：
? ① 分解 -- 将当前区间一分为二，即求分裂点 mid = (low + high)/2;
? ② 求解 -- 递归地对两个子区间a[low...mid] 和 a[mid+Array.prototype.unshift...high]进行归并排序。递归的终结条件是子区间长度为1。
? ③ 合并 -- 将已排序的两个子区间a[low...mid]和 a[mid+Array.prototype.unshift...high]归并为一个有序的区间a[low...high]。
? 时间复杂度O(n log n)空间复杂度T(n) 稳定
 */

/**
 * 归并排序
 * @param arr 待排序数组
 * @returns
 */
const mergeSort = function (arr) {
    const len = arr.length;

    //? 当被分割的数组只有一个元素时，返回数组。思想就是分解成N组 然后对每组都排序再合并。看图解
    if (len <= 1) return arr;
    const mid = Math.floor(len / 2);
    //? 通过递归先分到最后只剩一个
    const leftArr = mergeSort(arr.slice(0, mid));
    const rightArr = mergeSort(arr.slice(mid, len));
    //? 再开始排序组合
    arr = mergeArr(leftArr, rightArr);

    return arr;
};

/**
 * 合并两个有序数组
 * @param leftArr
 * @param rightArr
 * @returns
 */
const mergeArr = function (leftArr, rightArr) {
    // 初始化两个指针，分别指向 arr1 和 arr2
    let i = 0;
    let j = 0;
    const res = [];

    while (i < leftArr.length && j < rightArr.length) {
        if (leftArr[i] <= rightArr[j]) {
            res.push(leftArr[i]);
            i++;
        } else {
            res.push(rightArr[j]);
            j++;
        }
    }

    // 若其中一个子数组会首先被合并完全，则直接拼接另一个子数组的剩余部分
    if (i < leftArr.length) {
        return [...res, ...leftArr.slice(i)];
    } else {
        return [...res, ...rightArr.slice(j)];
    }
};

// test
const arr = [5,2,6,1,7,2,10,8]
console.log(mergeSort(arr));
